//
// Created by yangchao on 2022/6/8.
// 139. 单词拆分: https://leetcode.cn/problems/word-break/
//

#include <vector>
#include <string>
using namespace std;

//动态规划
class WordBreak {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        auto dp = vector<bool>(s.size()+1);
        dp[0] = true;
        for (int i = 0; i < s.size(); ++i) {
            if (!dp[i]) continue;   //只有前面的i个字符匹配上后面的匹配才有意义
            for (auto& word: wordDict) {
                if (word.size()+i <= s.size() && s.substr(i,word.size()) == word) {
                    //dp[j]=dp[i] && check(s[i..j-1])
                    dp[i+word.size()] = true;
                }
            }
        }
        return dp[s.size()];
    }
};

